import java.util.*;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public static int firstUniqChar(String s) {
        int[] count = new int[26];
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            count[ch-97]++;
        }
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(count[ch - 97] == 1){
                return i;
            }
        }
        return -1;
    }
    public Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node,Node> map = new HashMap<>();
        while(cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }


    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(String s : words){
            if(!map.containsKey(s)){
                map.put(s,1);
            }else{
                int val = map.get(s);
                map.put(s,val+1);
            }
        }


        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for(Map.Entry<String,Integer> entry: map.entrySet()){
            if(minHeap.size() < k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> peek = minHeap.peek();
                if(peek.getValue() < entry.getValue()){
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (peek.getValue().equals(entry.getValue())) {
                    if(entry.getKey().compareTo(peek.getKey()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }

        ArrayList<String> array = new ArrayList<>();
        for (int i = 0; i < k ; i++) {
            array.add(minHeap.poll().getKey());
        }
        Collections.reverse(array);
        return array;
    }
    public static void func(String s1,String s2){
        s1 = s1.toUpperCase();
        s2 = s2.toUpperCase();
        HashSet<Character> set = new HashSet<>();
        for(int i = 0; i< s2.length();i++){
            set.add(s2.charAt(i));
        }
        HashSet<Character> flg = new HashSet<>();
        for(int i = 0;i< s1.length();i++){
            if(!set.contains(s1.charAt(i))&&!flg.contains(s1.charAt(i))){
                flg.add(s1.charAt(i));
                System.out.print(s1.charAt(i));
            }
        }
    }


    public static void main(String[] args) {
        //Map<Integer,String> map = new HashMap<>();
        String[] words = {"hello","hello","world","world","abc","this","this","this"};
        topKFrequent(words,2);

    }
}